package 查找;

/**
 * @author Kevin
 * @Data 2021/2/16
 * 二分查找
 */
public class binarySearch {
    public static void main(String[] args) {
        int[] a = {2,1,9,8,5,6,7,};
        sort(a);
        int[] b = new int[a.length];
        for (int i = 0; i < a.length ; i++) {
            b[i]=a[i];
        }
//        System.out.println("所在位置："+searchOne(b,7));
        int result = searchTwo(b, 0,b.length,7);
        if (result > 0){
            System.out.println(result);
        }else{
            System.out.println("The key is not in the array");
        }
    }

    public static void sort(int[] L){
        for (int i = 0; i < L.length - 1; i++) {
            int min = i;
            for (int j = i; j < L.length; j++) {
                if (L[min] > L[j]){
                    min = j;
                }
            }
            if(i!= min){
                int temp = L[min];
                L[min] = L[i];
                L[i] = temp;
            }
        }
    }
    //迭代方法
    public static int searchOne(int[] L , int key){
        int first = 0;
        int last = L.length-1;
        while (first <= last){
        int mid = (first + last) /2;
            if (key == L[mid]){
                return mid;
            }else if(key < L[mid]){
                last = mid-1;
            }else{
                first = mid+1;
            }
        }
        return -1; //没有找到返回-1
    }
    //递归方法
    public static int searchTwo(int[] L ,int first ,int last ,int key){
        int result = 0;
        if (first > last){
            result = -1;
        }else{
            int mid = (first+last)/2;
            if (key == L[mid]){
                result = mid;
            }else if (key < L[mid]){
                last = mid-1;
                result = searchTwo(L , first ,last ,key);
            }else if (key > L[mid]){
                first = mid +1;
                result = searchTwo(L,first ,last ,key);
            }
        }
        return result;
    }
}
